//
// Created by isabella on 25-5-27.
//
#include <common.h>

class Solution {
public:
    int networkDelayTime(vector<vector<int> > &times, int n, int k) {
        int inf = INT_MAX / 2;
        vector dist(n, inf);
        vector visited(n, false);
        dist[k - 1] = 0;
        vector graph(n, vector(n, inf));
        for (int i = 0; i < n; i++) {
            graph[i][i] = inf;
        }
        for (int i = 0; i < times.size(); i++) {
            int from = times[i][0];
            int to = times[i][1];
            int weight = times[i][2];
            graph[from - 1][to - 1] = weight;
        }
        for (int i = 0; i < n; i++) {
            //找最小元素的下标
            int x = -1;
            for (int y = 0; y < n; y++) {
                if (!visited[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }

            visited[x] = true;
            for (int y = 0; y < n; y++) {
                dist[y] = min(dist[y], dist[x] + graph[x][y]);
            }
        }
        int ans = *max_element(dist.begin(), dist.end());
        return ans != inf ? ans : -1;
    }
};

int main() {
    auto sp = new Solution();
    vector<vector<int> > data = {{1, 2, 1}, {2, 3, 7}, {1, 3, 4}, {2, 1, 2}};
    sp->networkDelayTime(data, 3, 1);
    return 0;
}
